package com.fe.class05;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Description 迭代方式实现快排-V3.0
 * @Author sosuke :-)
 * @Date 2021/12/26 20:33
 */
public class Code06_QuickSortIteration {

    /**
     * 快排非递归版本需要的辅助类
     * 记录要处理的是什么范围上的排序
     */
    private static class Range {
        public int L;
        public int R;

        public Range(int L, int R) {
            this.L = L;
            this.R = R;
        }
    }

    /**
     * 迭代方式通过栈来记录要处理的排序范围（模拟递归过程）
     * @param arr
     */
    public static void quickSort(int[] arr) {
        if (null == arr || arr.length < 2) return;
        int N = arr.length;
        // 随机位置与最右侧位置交换，[0,N-1]随机值与N-1交换
        swap(arr, (int) (Math.random() * N), N - 1);
        int[] equalArea = netherLandsFlag02(arr, 0, N - 1);
        Stack<Range> rangeStack = new Stack<Range>();
        rangeStack.push(new Range(0, equalArea[0] - 1));
        rangeStack.push(new Range(equalArea[1] + 1, N - 1));
        while (!rangeStack.isEmpty()) {
            Range range = rangeStack.pop();
            if (range.L < range.R) {
                // 随机位置与最右侧位置交换，[range.L,range.R]随机值与range.R交换
                swap(arr, range.L + (int) (Math.random() * (range.R - range.L + 1)), range.R);
                equalArea = netherLandsFlag02(arr, range.L, range.R);
                rangeStack.push(new Range(range.L, equalArea[0] - 1));
                rangeStack.push(new Range(equalArea[1] + 1, range.R));
            }
        }
    }

    /**
     * 荷兰国旗问题，以arr[R]作为划分值，将arr划分成三部分
     * 先把arr[R]剔除，相当于在arr[L...R-1]中以arr[R]为标准划分为三部分
     *
     * @param arr
     * @param L
     * @param R
     * @return 返回等于区域的边界
     */
    private static int[] netherLandsFlag02(int[] arr, int L, int R) {
        if (L > R) return new int[]{-1, -1};
        if (L == R) return new int[]{L, L};
        // 设计两个窗口位置分别表示<arr[R]和>arr[R]
        int windowL = L - 1; //<arr[R]区域的右边界
        int windowR = R; //>arr[R]区域的左边界
        int curIndex = L;
        while (curIndex < windowR) { // 当前位置不能和>arr[R]区域的左边界撞上
            if (arr[curIndex] < arr[R]) {
                swap(arr, curIndex++, ++windowL);
            } else if (arr[curIndex] == arr[R]) {
                curIndex++;
            } else {
                swap(arr, curIndex, --windowR);
            }
        }
        // 最后将arr[R]加入进arr[L...R-1]中来
        swap(arr, windowR, R);
        return new int[]{windowL + 1, windowR};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int testTime = 50000; // 测试次数
        int maxSize = 100; // 数组数据个数
        int maxValue = 200; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            quickSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-? , +?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
}
